package com.future.offer;

import com.future.util.TreeNode;

import java.util.LinkedList;

/**
 * Description: 剑指 Offer 68 - I. 二叉搜索树的最近公共祖先
 * 输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
 * 输出: 6
 * 解释: 节点 2 和节点 8 的最近公共祖先是 6。
 *
 * @author weiruibai.vendor
 * Date: 2023/1/9 09:26
 */
public class Solution_68 {

    private static Solution_68 instance = new Solution_68();

    public static void main(String[] args) {
        TreeNode root = new TreeNode(6);
        root.left = new TreeNode(2);
        TreeNode p = new TreeNode(0);
        root.left.left = p;
        root.left.right = new TreeNode(4);


        root.right = new TreeNode(8);
        TreeNode q = new TreeNode(7);
        root.right.left = q;
        root.right.right = new TreeNode(9);
        TreeNode treeNode = instance.lowestCommonAncestor(root, p, q);
        System.out.println(treeNode);
    }


    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        LinkedList<TreeNode> stack = buildStack(root, p);
        LinkedList<TreeNode> stack1 = buildStack(root, q);
        TreeNode ans = stack1.pollFirst();
        TreeNode curNode = ans;
        while (stack.contains(curNode)) {
            ans = curNode;
            curNode = stack1.pollFirst();
        }
        return ans;
    }

    private LinkedList<TreeNode> buildStack(TreeNode root, TreeNode p) {
        LinkedList<TreeNode> stack = new LinkedList<>();
        TreeNode opNode = root;
        stack.add(opNode);
        int pVal = p.val;
        while (opNode != p) {
            if (opNode.val == pVal) {
                return stack;
            } else if (opNode.val < pVal) {
                stack.push(null);
                stack.addLast(opNode.right);// 注意：stack.push()等价于addFirst
                opNode = opNode.right;
            } else {
                stack.addLast(opNode.left);
                opNode = opNode.left;
            }
        }
        return stack;
    }
}
